• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
• Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
• Front: Get the front item from queue.
• Rear: Get the last item from queue.

Array = queue[N].
front = 0, rear = N-1.
N = 5.

Operation 1:
enque(5);
front = 0, 
rear = (N-1 + 1)%N = 0.
Queue contains: [5].

Operation 2:
enque(10);
front = 0, 
rear = (rear + 1)%N = (0 + 1)%N = 1.
Queue contains: [5, 10].

Operation 3:
enque(15);
front = 0, 
rear = (rear + 1)%N = (1 + 1)%N = 2.
Queue contains: [5, 10, 15].

Operation 4:
deque();
print queue[front]; 
front = (front + 1)%N = (0 + 1)%N = 1.
Queue contains: [10, 15].

10 enqueued to queue

20 enqueued to queue

30 enqueued to queue

40 enqueued to queue

10 dequeued from queue

Front item is 20

Rear item is 40

1. When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
2. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Queue in C++ STL

queue< data_type > queue_name;

where,
data_type is the type of element to be stored 
in the queue.
queue_name is the name of the queue data structure.

• empty() – Returns whether the queue is empty.
• size() – Returns the size of the queue.
• swap(): Exchange the contents of two queues but the queues must be of same type, although sizes may differ.
• emplace(): Insert a new element into the queue container, the new element is added to the end of the queue.
• front() and back(): front() function returns a reference to the first element of the queue. back() function returns a reference to the last element of the queue.
• push(g) and pop(): The push() function adds the element ‘g’ at the end of the queue. The pop() function deletes the first element of the queue.

The queue gquiz is : 10 20 30

gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() : 20 30

Queue interface in Java

• add()- This method is used to add elements at the tail of the queue. More specifically, at the last of linkedlist if it is used, or according to the priority in case of priority queue implementation.
• peek()- This method is used to view the head of a queue without removing it. It returns Null if the queue is empty.
• element()- This method is similar to peek(). It throws NoSuchElementException when the queue is empty.
• remove()- This method removes and returns the head of the queue. It throws NoSuchElementException when the queue is empty.
• poll()- This method removes and returns the head of the queue. It returns null if the queue is empty.
• size()- This method returns the no. of elements in the queue.

Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4

A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Why have we taken a pointer that points to the last node instead of first node?

6 4 2 8 12 10

1. Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
2. Useful for implementation of a queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as the next of last.
3. Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4. Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

• Method 1 (By making push operation costly): This method makes sure that newly entered element is always at the front of 'q1', so that pop operation just dequeues from 'q1'. The queue, 'q2' is used to put every new element at front of 'q1'.
  
  

  push(s, x) // x is the element to be pushed and s is stack
    1) Enqueue x to q2
    2) One by one dequeue everything from q1 and enqueue to q2.
    3) Swap the names of q1 and q2 
  // Swapping of names is done to avoid one more  
  // movement of all elements from q2 to q1. 
  
  pop(s)
    1) Dequeue an item from q1 and return it.
  

  
  Implementation:
  
  C++

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Java

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Output :
  

  current size: 3
  3
  2
  1
  current size: 1
  

• Method 2 (By making pop operation costly): In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.
  
  

  push(s,  x)
    1) Enqueue x to q1 (assuming size of q1 is unlimited).
  
  pop(s)  
    1) One by one dequeue everything except the last element 
       from q1 and enqueue to q2.
    2) Dequeue the last item of q1, the dequeued item 
       is the result, store it.
    3) Swap the names of q1 and q2
    4) Return the item stored in step 2.
  // Swapping of names is done to avoid one more
  // movement of all elements from q2 to q1.
  

  
  
  Implementation:
  
  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  Run
  Output :

  current size: 4
  4
  3
  2
  current size: 2
  

• Method 1 (By making enQueue operation costly): This method makes sure that oldest entered element(element inserted first) is always at the top of stack1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used. The idea is to while pushing an element, first move all elements from stack1 to stack2, insert the new element to stack1 and then again move all elements from stack2 to stack1.
  
  Below is the implementation of both enQueue() and deQueue() operations:
  

  enQueue(q, x)
    1) While stack1 is not empty, push everything from stack1 to stack2.
    2) Push x to stack1 (assuming size of stacks is unlimited).
    3) Push everything back to stack1.
  Here the time complexity will be O(n)
  
  deQueue(q)
    1) If stack1 is empty then print an error
    2) Pop an item from stack1 and return it
  Here time complexity will be O(1)
  

  
  Implementation:
  
  C++

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Java

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Output:

  1
  
  2
  
  3

• Method 2 (By making deQueue operation costly): In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally, the top of stack2 is returned.
  
  Below is the implementation of both enQueue() and deQueue() operations:
  

  enQueue(q,  x)
    1) Push x to stack1 (assuming size of stacks is unlimited).
  Here time complexity will be O(1)
  
  deQueue(q)
    1) If both stacks are empty then error.
    2) If stack2 is empty
         While stack1 is not empty, push everything from stack1 to stack2.
    3) Pop the element from stack2 and return it.
  Here time complexity will be O(n)
  

  
  Method 2 is better in performance than method 1. As Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 is empty.
  
  Implementation :
  
  
  C++

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Java

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Output:

  1 2 3 

Problem #1 : Reversing the first K elements of a Queue

• enqueue(x) : Add an item x to rear of queue
• dequeue() : Remove an item from front of queue
• size(( : Returns number of elements in queue.
• front() : Finds front item.

Input : Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
        k = 5
Output : Q = [50, 40, 30, 20, 10, 60, 70, 80, 90, 100]

1. Create an empty stack.
2. One by one dequeue items from a given queue and push the dequeued items to stack.
3. Enqueue the contents of stack at the back of the queue.
4. Reverse the whole queue.

/* Function to reverse the first K elements of the Queue */
void reverseQueueFirstKElements(k, Queue) 
{ 
    if (Queue.empty() == true || k > Queue.size()) 
        return
    if (k <= 0) 
        return
    stack  Stack 
    /* Push the first K elements into a Stack*/
    for ( i = 1 to k) { 
        Stack.push(Queue.front())
        Queue.pop()
    } 
    /* Enqueue the contents of stack 
       at the back of the queue*/
    while (!Stack.empty()) { 
        Queue.push(Stack.top())
        Stack.pop()
    } 
    /* Remove the remaining elements and  
       enqueue them at the end of the Queue*/
    for (int i = 0 to i < Queue.size() - k) { 
        Queue.push(Queue.front())
        Queue.pop()
    } 
} 

Problem #2 : Sliding Window Maximum

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3 
Output :
3 3 4 5 5 5 6

void printKMax(arr[], n, k) 
{ 
    // Create a Double Ended Queue, Qi that will store indexes of array elements 
    // The queue will store indexes of useful elements in every window and it will 
    // maintain decreasing order of values from front to rear in Qi, i.e., 
    // arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order 
    deque < int > Qi(k)
  
    /* Process first k (or first window) elements of array */
    for (i = 0; i < k; ++i) { 
        // For every element, the previous smaller elements are useless so 
        // remove them from Qi 
        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) 
            Qi.pop_back() // Remove from rear 
  
        // Add new element at rear of queue 
        Qi.push_back(i)
    } 
  
    // Process rest of the elements, i.e., from arr[k] to arr[n-1] 
    for (; i < n; ++i) { 
        // The element at the front of the queue is the largest element of 
        // previous window, so print it 
        print (arr[Qi.front()]) 
  
        // Remove the elements which are out of this window 
        while ((!Qi.empty()) && Qi.front() <= i - k) 
            Qi.pop_front() // Remove from front of queue 
  
        // Remove all elements smaller than the currently 
        // being added element (remove useless elements) 
        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) 
            Qi.pop_back()
  
        // Add current element at the rear of Qi 
        Qi.push_back(i)
    } 
  
    // Print the maximum element of last window 
    print (arr[Qi.front()]) 
}